package com.fwpsl.sort;

import java.util.Arrays;

/**
 * @author: 风戏fw
 * @date: 2024/1/24
 * @description:
 */
public class Sort {

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        // 每次需要排序的长度
        for (int i = arr.length - 1; i > 0; i--) {
            // 从第一个元素到第i个元素
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 冒泡排序逻辑优化，增加swap标志
     * 当前一轮没有进行交换，说明数组已有序，不用再进行下一轮的循环了，直接退出。
     *
     * @param arr
     */
    public static void bubbleSort2(int[] arr) {
        boolean swap;
        // 每次需要排序的长度
        for (int i = arr.length - 1; i > 0; i--) {
            swap = false;
            // 从第一个元素到第i个元素
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swap = true;
                }
            }

            if (swap == false) {
                break;
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 循环查找最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            int value = arr[i];
            int position = i;
            while (position > 0 && arr[position - 1] > value) {
                arr[position] = arr[position - 1];
                position--;
            }
            arr[position] = value;
        }
    }

    /**
     * 折半插入排序
     *
     * @param arr
     */
    public static void bInsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            int value = arr[i];
            int low = 1, high = i - 1;
            while (low <= high) {
                int m = (low + high) / 2;
                if (value < arr[m]) {
                    high = m - 1;
                } else {
                    low = m + 1;
                }
            }

            for (int j = i - 1; j >= high + 1; --j) {
                arr[j + 1] = arr[j];
            }
            arr[high + 1] = value;
        }
    }

    /**
     * 希尔排序
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int temp;
        // 对每个增量进行一次排序
        for (int delta = arr.length / 2; delta >= 1; delta /= 2) {
            for (int i = delta; i < arr.length; i++) {
                // 注意每个地方增量和差值都是delta
                for (int j = i; j >= delta && arr[j] < arr[j - delta]; j -= delta) {
                    temp = arr[j - delta];
                    arr[j - delta] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("增量：" + delta + "当前顺序：" + Arrays.toString(arr));
        }
    }

    /**
     * O(n3/2) by Knuth
     *
     * @param arr
     */
    public static void shellSort2(int[] arr) {
        int delta = 1;
        while (delta < arr.length / 3) {//generate delta
            delta = delta * 3 + 1;    // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
        }
        int temp;
        for (; delta >= 1; delta /= 3) {
            for (int i = delta; i < arr.length; i++) {
                for (int j = i; j >= delta && arr[j] < arr[j - delta]; j -= delta) {
                    temp = arr[j - delta];
                    arr[j - delta] = arr[j];
                    arr[j] = temp;
                }
            }//loop i
        }//loop delta
    }

    public static void main(String[] args) {
        int[] arr = new int[]{15, 38, 84, 11, 3, 38, 91, 13, 65, 49, 43};
        System.out.println("before sort:" + Arrays.toString(arr));

        // 冒泡排序
//        bubbleSort(arr);
        // 冒泡排序逻辑优化，增加swap标志
//        bubbleSort2(arr);

        // 选择排序
//        selectionSort(arr);

        // 插入排序
//        insertionSort(arr);

        // 希尔排序
        shellSort(arr);

        System.out.println("after sort:" + Arrays.toString(arr));
    }


}
